CF799D Field expansion

题解：

虽然n给的范围很大，但首先要明确，最坏情况下也至多操作34次，因为$a,b\leq2^{17}$，所以34之后的操作都可以无视

这其实就说明这道题可以用指数级算法解决，如bfs

考虑在bfs设两个参数$x$和$y$，分别表示两边的目标放大倍数，并且使$x<y$

贪心的，操作肯定是从大到小选的

这样每次操作至多只会产生两种新状态，要么在$x$中砍掉一定倍数，要么在$y$中砍掉一定倍数

如果某个时刻$x$和$y$都等于1了，就说明已经合法，输出答案

否则到不了就无解输-1

下面的代码看起来可能是$2^{34}$的，但其实是$2^{17}$的，因为在一边达到目标倍数后，它的x就一直会保持1的状态被map记录下，不再增加新状态，从而就从双选变成单选了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define pii pair<int,int>
#define x first
#define y second

const int N=1e5+5;
int a,b,h,w,n,val[N];
queue<pii> q;
map<pii,int> v; //map记录该状态有没有走过，至少走几步

pii adjust(pii x){ //维护x和y，使得x始终y
    if(x.x>x.y) swap(x.x,x.y);
    return x;
}

int divi(int x,int y){ //计算目标放大倍数
    return x/y+(x%y!=0);
}

signed main(){
    read(a);read(b);read(h);read(w);read(n);
    for(int i=1;i<=n;i++) read(val[i]);
    sort(val+1,val+1+n,greater<int>()); //倒着排序
    int lim=min(34,n); //最大操作次数
    pii hii=pii(divi(a,h),divi(b,w)),wii=pii(divi(a,w),divi(b,h)); //旋转也可以，所以有两种起始状态
    v[hii]=v[wii]=1; //起始步数为1
    q.push(hii);
    q.push(wii);
    while(!q.empty()){ //bfs
        pii now=q.front();
        q.pop();
        int step=v[now];
        if(now.x==1&&now.y==1){
            write(step-1); //操作次数=步数-1
            return 0;
        }
        if(step>lim) continue;
        pii nxt=adjust(pii(divi(now.x,val[step]),now.y)); //该操作给x
        if(v[nxt]==0){ //没有走过就走
            v[nxt]=step+1;
            q.push(nxt);
        }
        nxt=adjust(pii(now.x,divi(now.y,val[step]))); //该操作给y
        if(v[nxt]==0){
            v[nxt]=step+1;
            q.push(nxt);
        }
    }
    write(-1);
}